from LeetCoder import *


class Solution:

    def minimumCost(self, s: str) -> int:
        n = len(s)
        l0 = [inf] * n
        l1 = [inf] * n
        l0[0] = 0 if s[0] == '0' else 1
        l1[0] = 1 if s[0] == '0' else 0
        for i in range(1, n):
            v = s[i]
            if v == '0':
                l0[i] = min(l0[i - 1], l1[i - 1] + i)
                l1[i] = i + 1 + l0[i - 1]
            else:
                l0[i] = i + 1 + l1[i - 1]
                l1[i] = min(l1[i - 1], l0[i - 1] + i)
        r0 = [inf] * n
        r1 = [inf] * n
        r0[-1] = 0 if s[-1] == '0' else 1
        r1[-1] = 1 if s[-1] == '0' else 0
        for i in range(n - 2, -1, -1):
            v = s[i]
            if v == '0':
                r0[i] = min(r0[i + 1], r1[i + 1] + n - i - 1)
                r1[i] = n - i + r0[i + 1]
            else:
                r0[i] = n - i + r1[i + 1]
                r1[i] = min(r1[i + 1], r0[i + 1] + n - i - 1)
        ans = min(r0[0], r1[0], l0[-1], l1[-1])
        for i in range(1, n):
            ans = min(ans, l0[i - 1] + r0[i], l1[i - 1] + r1[i])
        return ans
s = Solution()
print(s.minimumCost("000000011"))
print(s.minimumCost("0011"))
print(s.minimumCost("010101"))
